#leetcode题目89：格雷编码
#难度：简单

from typing import List

class Solution:
    def grayCode(self, n: int) -> List[int]:
        res = [0]
        head = 1
        for i in range(n):
            for j in range(len(res)-1, -1, -1):
                res.append(res[j] + head)
            head <<= 1
        return res


#测试数据
n = 2
#预期输出：[0,1,3,2]
solution = Solution()
print(solution.grayCode(n))

n = 1
#预期输出：[0,1]
solution = Solution()
print(solution.grayCode(n))

n = 3
#预期输出：[0,1,3,2,6,7,5,4]
solution = Solution()
print(solution.grayCode(n))